#include <stdio.h>
#include <string.h>

void get_next(const char *T, int lenOfT, int *next)
{
	int i = 0;
	int j = -1;
	next[0] = -1;
	while (i < lenOfT)
	{
		if (j == -1 || T[i] == T[j])
		{
			next[++i] = ++j;
		}
		else
		{
			j = next[j];
		}
	}
}

int index_KMP(const char *S, int lenOfS, const char *T, int lenOfT, int pos)
{
	int i = pos;
	int j = 0;
	int next[lenOfT];
	get_next(T, lenOfT, next);
	while (i < lenOfS && j < lenOfT)
	{
		if (j == 0 || S[i] == T[j])
		{
			i++;
			j++;
		} else
		{
			j = next[j];
		}
	}
	if (j == lenOfT) 
	{
		return i - j;
	}
	else
	{
		return -1;
	}
}

int main(void)
{
	char *s = "this is a good program!";
	char *t = "good";
	int index = index_KMP(s, strlen(s), t, strlen(t), 0);
	printf("the index of %s is: %d\n", t, index);
	return 0;
}